package likou;

public class _552 {
    public static void main(String[] args) {

    }

    public int checkRecord(int n) {
        long[][][] dp = new long[2][3][n + 1];   //dp[i][j][k]表示有i个A,结尾是连续j个L,长度为k的字符串所代表的组合数
        dp[0][0][1] = 1;
        dp[1][0][1] = 1;
        dp[0][1][1] = 1;

        for (int len = 2; len <= n; ++len) {
            dp[0][0][len] = (dp[0][0][len - 1] + dp[0][1][len - 1] + dp[0][2][len - 1]) % 1000000007;
            dp[1][0][len] = (dp[0][0][len - 1] + dp[0][1][len - 1] + dp[0][2][len - 1] + dp[1][0][len - 1] + dp[1][1][len - 1] + dp[1][2][len - 1]) % 1000000007;
            dp[0][1][len] = dp[0][0][len - 1] % 1000000007;
            dp[1][1][len] = dp[1][0][len - 1] % 1000000007;
            dp[0][2][len] = dp[0][1][len - 1] % 1000000007;
            dp[1][2][len] = dp[1][1][len - 1] % 1000000007;
        }
        return (int) ((dp[0][0][n] + dp[1][0][n] + dp[0][1][n] + dp[1][1][n] + dp[0][2][n] + dp[1][2][n]) % 1000000007);
    }




    public int checkRecord2(int n) {
        long[][] a = new long[][]{{1},{1},{0},{1},{0},{0}};
        long[][] aMatrix = new long[][]{{1,1,1,0,0,0},{1,0,0,0,0,0},{0,1,0,0,0,0},{1,1,1,1,1,1},{0,0,0,1,0,0},{0,0,0,0,1,0}};
        while (n>0) {
            int m = n & 1;
            if (m == 1) {
                a = this.multipleMatrix(aMatrix, a);
            }
            aMatrix = this.multipleMatrix(aMatrix, aMatrix);
            n = n>>1;
        }
        /**
         * 0 A0L0
         * 1 A0L1
         * 2 A0L2
         * 3 A1L0
         * 4 A1L1
         * 5 A1L2
         */
        return (int)a[3][0];

    }
    public long[][] multipleMatrix(long[][] a,long[][] b) {
        long mod = (long)1e9+7;
        long c[][] = new long[a.length][b[0].length];
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < b[i].length; j++) {
                for (int k = 0; k < a[i].length; k++) {
                    c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % mod;
                }
            }
        }
        return c;
    }
}
